package com.example.demo.zaqizabatest.sortalgorithm;

/**
 *
 * 从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
 *
 * 在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
 *
 * @ClassName BubbleSort 冒泡排序
 * @Author lys4134
 * @Date 2021/12/29 09:47:33
 * @Description BubbleSort
 * @Version 1.0
 **/
public class  BubbleBaseSort<T extends Comparable<T>> extends BaseSort<T> {

    @SuppressWarnings("AlibabaLowerCamelCaseVariableNaming")
    @Override
    public void sort(T[] nums) {
        final int N = nums.length;
        boolean isSorted = false; // 判断剩余是否有序
        for (int i = N - 1; i > 0 && !isSorted; i--) { // 先找到最大的放最右侧，从剩下的元素中再找出最大的.....
            isSorted = true;  // 默认有序
            for (int j = 0; j < i; j++) {
                if (less(nums[j + 1], nums[j])) { // 找到逆序的两个元素，交换位置，并标注数组是无序的
                    isSorted = false;
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    /**
     * 泛型的方法都是复制过来的，自己在上面加了写注释，int类型为自己写的
     * @param nums
     */
    public void sort(int[] nums) {
        int length = nums.length;
        boolean isSorted = false; // 判断剩余是否有序,有序则不需要继续遍历
        for(int i = length-1; i >= 0 && !isSorted; i--){  // 由于是先找最右侧的数据，所以需要逆序遍历
            isSorted = true; // 假设剩余数据皆为有序
            for (int j = 0; j < i; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    isSorted = false;
                }
            }
        }
    }


    public void sort1(int[] nums) {
        int length = nums.length;
        for(int i = length-1; i >= 0; i--){  // 由于是先找最右侧的数据，所以需要逆序遍历
            for (int j = 0; j < i; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }


        for (int i = length-1; i >=0; i--) {
            for (int j = 0; j < i; j++) {
                if(nums[j] > nums[j+1]){
                    int temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        BubbleBaseSort<Integer> bubbleSort = new BubbleBaseSort();
        int[] nums = new int[5];
        nums[0] = 3;nums[1] = 5;nums[2] = 2;nums[3] = 4;nums[4] = 1;
        bubbleSort.sort(nums);
        bubbleSort.print(nums);
    }
}
